package daily.year2024.m11;

import java.util.*;

/**
 * No.165 比较版本号
 *
 * @author wjs 2024/11/9
 */
public class d9 {
    //双指针解法
    class Solution {
        public int compareVersion(String version1, String version2) {
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            queue.poll();
            char[] chars1 = version1.toCharArray(), chars2 = version2.toCharArray();
            int n = chars1.length, m = chars2.length;
            int i = 0, j = 0;
            while(i < n || j < m) {
                int v1 = 0, v2 = 0;
                while(i < n && chars1[i] != '.') {
                    v1 = v1 * 10 + (chars1[i] - '0');
                    i++;
                }
                while(j < m && chars2[j] != '.') {
                    v2 = v2 * 10 + (chars2[j] - '0');
                    j++;
                }
                if(v1 > v2) {
                    return 1;
                }
                if(v1 < v2) {
                    return -1;
                }
                i++;
                j++;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        removeKdigits("1432219", 3);
        Queue<int[]> queue = new LinkedList<>();
        queue.peek();
    }

    public static String removeKdigits(String num, int k) {
        char[] chars = num.toCharArray();
        int n = chars.length;
        char[] stack = new char[n];
        int l = 0, remain = n-k;
        for(int i=0;i < n && k > 0;i++) {
            while(l > 0 && k > 0 && stack[l-1] > chars[i]) {
                l--;
                k--;
            }
            stack[l] = chars[i];
            l++;
        }
        StringBuilder sb = new StringBuilder();
        boolean hasNum = false;
        for(int i=0;i < remain;i++) {
            if(stack[i] != '0') {
                hasNum = true;
                sb.append(stack[i]);
            } else if(hasNum) {
                sb.append(stack[i]);
            }
        }
        return sb.toString();
    }
}
